package sword.offer.common;

import java.util.*;

/**
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class GenerateTree {
    public static void main(String[] args) {
        List<Integer> nodes = new ArrayList<>();
        nodes.add(1);
        nodes.add(2);
        nodes.add(null);
        nodes.add(5);
        nodes.add(6);
        nodes.add(7);
        nodes.add(null);
        Node node = generateTree(nodes);
        System.out.println(node);
    }
    /**
     * 根据val来生成一棵树
     * 层序构建二叉树，利用BFS的思想
     * @return 树的根节点
     * */
    public static Node generateTree(List<Integer> values){
        Deque<Node> deque = new ArrayDeque<>();
        int k = 0;
        Node head = new Node(values.get(k++));
        deque.addLast(head);
        while(!deque.isEmpty() && k < values.size()-1){
            Node node = deque.removeFirst();
            node.left = Objects.isNull(values.get(k)) ? null : new Node(values.get(k));
            k++;
            node.right = Objects.isNull(values.get(k)) ? null : new Node(values.get(k));
            k++;
            if(node.left != null) { deque.addLast(node.left);}
            if(node.right != null) { deque.addLast(node.right);}
        }
        return head;
    }

    public static TreeNode generateTree1(List<Integer> values){
        Deque<TreeNode> deque = new ArrayDeque<>();
        int k = 0;
        TreeNode head = new TreeNode(values.get(k++));
        deque.addLast(head);
        while(!deque.isEmpty() && k < values.size()-1){
            TreeNode node = deque.removeFirst();
            node.left = Objects.isNull(values.get(k)) ? null : new TreeNode(values.get(k));
            k++;
            node.right = Objects.isNull(values.get(k)) ? null : new TreeNode(values.get(k));
            k++;
            if(node.left != null) { deque.addLast(node.left);}
            if(node.right != null) { deque.addLast(node.right);}
        }
        return head;
    }
}
